The Maze
Understand and solve the interview question "The Maze".
We'll cover the following
Description#
The maze is a puzzle game where the ball moves in the available empty spaces. The player aims to get the ball to the specified destination. The ball can go through the empty spaces by rolling up, down, left, or right, but it will not stop rolling until it hits a wall or reaches the destination and then hits a wall or reaches the end of a grid. After hitting a wall, the ball will choose the next direction before moving forward. The borders of the maze are considered walls.
Constraints#
maze[i][j]must be0or1, initially.mazeLength==maze.lengthmazeSubarrayLength==maze[i].length- 1 <=
mazeLength,mazeSubarrayLength<= 100 start.length,end.length== 2- 0 <= , <=
mazeLength - 0 <= , <=
mazeSubarrayLength - The ball and the destination must exist in an empty space and, initially, they will not be in the same position.
- The maze must contain at least two empty spaces.
Let’s see how the maze game looks in the illustration below:
Coding exercise#
Solution#
We can consider the given maze as a depth-first search tree. The starting position will represent the root node of the tree. We will choose one path at a time and try to go as deep as possible into the levels of the tree before opting for the next path. We will have four possible directions on each position, that is, left, right, up, or down, except for the borders of the maze. Thus, the ball will start traversing from the root node over the branch, and the new position will be represented as an empty space or a wall.
Let’s see the following algorithm to implement the described problem.
-
We are given a 2D array named
maze. -
We are also given the coordinates of a start and end cell. We will use a hash map named
visited_placesto keep track of the cells that have already been visited. -
We will move continuously in either the left, right, upward, or downward direction from every starting position till we reach the boundary or a wall.
-
The empty space is represented by 0, a wall is represented by 1.
-
From the starting position, we will determine all the endpoints that can be reached by choosing the four directions. For each case, the new endpoint will act as the new starting point for the traversals.
-
When we move to the next empty space in any direction, we will update the current index value in the
visited_placestoTrue. -
We will call the
pathfunction in each direction recursively, and each time we will use the previously obtained starting point. -
At the end, when the starting position and the destination are the same, we will return
True. Otherwise, we will update the current position in thevisited_placestoTrueand returnFalse.
Let’s understand this algorithm with the illustration given below:
1 of 12
2 of 12
3 of 12
4 of 12
5 of 12
6 of 12
7 of 12
8 of 12
9 of 12
10 of 12
11 of 12
12 of 12
Let’s look at the solution below:
Complexity measures#
| Time complexity | Space complexity |
|---|---|
Time complexity#
We will traverse the complete maze in the worst-case scenario, so the time complexity will be , wherein will be the size of the row and will be the size of the column.
Space complexity#
In the worst-case scenario, the call stack depth will be . Therefore, the space complexity will be .
Design Tic-Tac-Toe
Restore IP Addresses